from math import *
from datetime import *

def get_lon_midpoint(lon1,lon2):
    #check to see if we are crossing the pm
    if 180 < (abs(lon1 - lon2)):
        #if yes, correct calculation of midpoint
        mid = 180-abs(lon1)
        mid += 180-abs(lon2)
        mid = mid/2
        if lon1 < lon2:
            lonm = lon1 - mid
        else:
            lonm = lon2 - mid
        if lonm<-180:
            lonm = lonm+360
    else:
        lonm = (lon1+lon2)/2
    return lonm
    
def get_linestring(lat0,lon0,alt0,lat1,lon1,alt1):
    #the number of linesegments
    steps = 20
    
    #latitude calculations
    lat_step = (lat1-lat0)/float(steps)
    lats = [lat0]
    ct = 1
    while ct < (steps-1):
        lats.append(lat0+(lat_step*ct))
        ct += 1
    lats.append(lat1)
    
    #altitude calculations
    alt_step = (alt1-alt0)/float(steps)
    alts = [alt0]
    ct = 1
    while ct < (steps-1):
        alts.append(alt0+(alt_step*ct))
        ct += 1
    alts.append(alt1)
    
    #longitude calculations including great circle
    # great circle if flag gets set to 1
    flag = 0
    if 180 < (abs(lon0 - lon1)):
        flag = 1
        t = 180-abs(lon0)
        t += 180-abs(lon1)
        lon_step = t/float(steps)
        if lon0<lon1:
            lon_step = lon_step * -1
    else:
        lon_step = (lon1-lon0)/float(steps)
        lons = [lon0]
        ct = 1
        while ct < (steps-1):
            lons.append(lon0+(lon_step*ct))
            ct += 1
        lons.append(lon1)
        
        
    if flag == 1:
        lons = [lon0]
        ct = 1
        while ct < (steps-1):
            cur = lon0+(lon_step*ct)
            if -180 < cur and cur < 180:  
                lons.append(cur)
            elif cur < -180:
                over = (cur + 180)
                cur = 180 + over 
                lons.append(cur)
            else:
                over = (cur - 180)
                cur = -180 + over 
                lons.append(cur)
            ct += 1
        lons.append(lon1)
        
    ct = 0
    linestring = ''
    while ct < len(lats):
        linestring += str(lons[ct])+','+str(lats[ct])+','+str(int(alts[ct]))+' \n'
        ct+=1
    return linestring
    
    
    
    
def build_kml(tree,coords,mydomain,branch_color,branch_width,node_url,alt_grow,proximity,kml_title):

    if tree.count('(') != tree.count(')'):
        return 'error','Your tree contains '+str(tree.count('('))+' open parenthesis "(" and '+str(tree.count(')'))+' close parenthesis ")" '
    #variables:
    # proximity
    # alt_grow
    # internal_icon
    # default_color
    
    internal_icon = str(node_url) 
    
    default_color = str(branch_color)
    
    alt_grow = int(alt_grow)
    
    #this sets the number of decimals to round coordinates to when
    #looking for points sharing the same location
    proximity = int(proximity)
    #set the radius size of the circle to scatter them around
    offset = (1*10**(-1*proximity))*.75
    
    coords = coords.strip()
    tree = tree.strip()
    
    coords = coords.split('\n')
    lat = {}
    lon = {}
    #track unique coords in order to implement scatter of those overlapping
    uniques = {}
    tstamps = False
    maxtime = datetime.min
    
    icons = {}
    for line in coords:
        if line != '':
            curr = line.split(',')
            if 3 <= len(curr):
                lat[curr[0]] = curr[1].strip()
                lon[curr[0]] = curr[2].strip()
                
                title = str(round(float(curr[1]),proximity))+'_'+str(round(float(curr[2]),proximity))
                n = 0
                if title in uniques:
                    n = int(uniques[title])
                uniques[title] = n + 1
                
                
                if 4 <= len(curr):
                    if curr[3].strip() == '':
                        icons[curr[0]] = 'default'
                    else:
                        icons[curr[0]] = curr[3].strip()
                    
                    
                    #if datetime set in CSV, extract and store in dictionary
                    if 5 <= len(curr):
                        #date
                        #format= year-mm-day:hour:
                        if tstamps == False:
                            tstamps = {}
                        if len(str(curr[4].strip())) != 0:
                            curdate = curr[4].strip().split('-')
                            yr = int(curdate[0])
                            tmp_date = datetime(yr,01,01)
                            if 2 <= len(curdate):
                                mn = int(curdate[1])
                                tmp_date = tmp_date.replace(month = mn)
                                if 3 <= len(curdate):
                                    daytime = curdate[2].split('T')
                                    dy = int(daytime[0])
                                    tmp_date = tmp_date.replace(day = dy)
                                    if 2 <= len(daytime):
                                        daytime = daytime[1].split(':')
                                        hr = int(daytime[0])
                                        tmp_date = tmp_date.replace(hour = hr)
                                        if 2 <= len(daytime):
                                            mt = int(daytime[1])
                                            tmp_date = tmp_date.replace(minute = mt)
                                            if 3 <= len(daytime):
                                                sc = int(daytime[2])
                                                tmp_date = tmp_date.replace(second = sc)
                            tstamps[curr[0]] = tmp_date   
                            if maxtime < tmp_date:
                                maxtime = tmp_date
                    
                else:
                    icons[curr[0]] = 'default'
                    
    used_uniques = {}
    for i,t in uniques.items():
        if 1< int(t):
            used_uniques[i] = 0
    
    
            
            
                
    tree = tree.replace('\n','')    
    tree = tree.split(',')
    anc = []

    leafs = []
    nodes = []
    rank = {}
    altitude = {}
    #altitude growth is for now very basic, just linear growth in meters
    #need to implement a better method that grows the tree by the geographic spread of a nodes's
    #descendants

    #desc, anc
    tree_struc = {}

    #name, rank
    tree_rank = {}
    flag = 0
    for tree_char in tree:
    
        #open parenths to anc list
        while list(tree_char)[0] == '(':
            anc.append(0)
            tmp = list(tree_char)
            tmp.pop(0)
            tree_char = ''.join(tmp)
        
        #find out if the next value is a leaf
        tmp = tree_char.split(':')
        name = tmp[0]
        x = 1
        #find out the leaf's ancestor node
        while anc[-x] == 2:
            x += 1
        #add the leaf and ancestor to the dictionary
        tree_struc[name] = len(anc) - x
        leafs.append(name)
        rank[name] = 0
        
        #the ancestor now becomes the current working node
        curr = len(anc)-x
        
        #let the anc array know that another daughter has been found for the working node
        anc[-x] = anc[-x]+1
        
        #find out how many clades are closed in the working string (tree_char)
        tmp.pop(0)
        tmp = ':'.join(tmp)
        stops = tmp.count(")")
        
        ct = 0
        #for each closed clade, add the working node and its anc to the anc array
        #move the working node up to the last anc
        while ct < stops:
            x = 1
            while anc[-x] == 2:
                x += 1
                
            tree_struc[curr] = len(anc) - x
            
            if x<len(anc):
                anc[-x] = anc[-x]+1
            
            curr = len(anc) - x
            ct+=1
        flag = 1
        
    #this function scatters any points of shared radius = 'offset'
    #around a circle at equal distances
    #if timestamps were given, it also fills any black timestamps with the maxtime value
    for nm in leafs:
        if tstamps != False:
            if nm not in tstamps:
                tstamps[nm] = maxtime
        curla = float(lat[nm])
        curlo = float(lon[nm])
        title = str(round(float(curla),proximity))+'_'+str(round(float(curlo),proximity))
        if title in used_uniques:
            total = uniques[title]
            used = int(used_uniques[title])
            
            #scatter points sharing lat/lon around a circle of radius = 'offset'

            angle = float(360)/(total)
            angle = radians(angle*used)
            tmpx = cos(angle) * offset
            tmpy = sin(angle) * offset
            tmpx += -offset
            tmpy += -offset
            tmp_lon = curlo + tmpx
            tmp_lat = curla + tmpy
            
            if tmp_lon < -180:
                tmp_lon += 360
            elif 180 < tmp_lon:
                tmp_lon += -360
            
            lat[nm] = round(float(tmp_lat),6)
            lon[nm] = round(float(tmp_lon),6)
                
            used_uniques[title] = used+1
            
            
            
    for t,n in tree_struc.items():
        if t not in leafs:
            if n not in nodes:
                nodes.append(n)
        if n not in nodes:
            nodes.append(n)


    #Iterate over the tree to find the rank of all internal nodes       
    tmp_nodes = nodes
    global_max = 0
    while len(rank) != len(tree_struc)-1:
        new_tmp_nodes = []
        for n in tmp_nodes:
            max_rank = -1
            chld1 = [k for k, v in tree_struc.iteritems() if v == n][0]
            chld2 = [k for k, v in tree_struc.iteritems() if v == n][1]
            if chld1 in rank:
                max_rank = rank[chld1]
                if chld2 in rank:
                    if max_rank < rank[chld2]:
                        max_rank = rank[chld2]
                else:
                    max_rank = -1
            if max_rank != -1:
                rank[n] = max_rank + 1
                if global_max < max_rank:
                    global_max = max_rank+1
            else:
                new_tmp_nodes.append(n)
        tmp_nodes = new_tmp_nodes
    rank[0] = global_max+1      

    if len(leafs) != len(lat) or len(leafs) != len(lon):
        return 'error',str(len(leafs))+' tips existed in your tree and '+str(len(lat))+' lat and '+str(len(lon))+' lon existed'

    #sort the rank dictionary so lowest ranked nodes are first
    rank = sorted(rank.items(),reverse=True)

    lstring_flag = [] #used to later deterime if a branch is a rectangular cladogram
    
    #set the altitude,lat,lon for each internal node
    for n,r in rank:
        altitude[n] = 0
        if 0 < r:
            
            # get the names of the node's two children
            # because the root node '0' tops the tree stuc as an anc of itself '0:0' 
            # these little chldz loops will block that from entering this calc
            z = 0
            chld1 = [k for k, v in tree_struc.iteritems() if v == n][z]
            if chld1 == n:
                z += 1
                chld1 = [k for k, v in tree_struc.iteritems() if v == n][z]
            z += 1
            chld2 = [k for k, v in tree_struc.iteritems() if v == n][z]
            if chld2 == n:
                z += 1
                chld2 = [k for k, v in tree_struc.iteritems() if v == n][z]
            
            #if timestamps set, look up max timestamp of children
            if tstamps != False:
                t1 = datetime.max
                t2 = datetime.max
                if chld1 in tstamps:
                    t1 = tstamps[chld1]
                if chld2 in tstamps:
                    t2 = tstamps[chld2]
                curdate = min(t1,t2)
                if curdate != datetime.max:
                    tstamps[n] = curdate
                

            #look up the child altitudes
            alt1 = float(altitude[chld1])
            alt2 = float(altitude[chld2])
            
            
            #look up the child latitudes
            lat1 = float(lat[chld1])
            lat2 = float(lat[chld2])
            #set new latitude for working node
            latm = (lat1 + lat2)/2
            lat[n] = latm
                
            lon1 = float(lon[chld1])
            lon2 = float(lon[chld2])
            
            lonm = get_lon_midpoint(lon1,lon2)
            lon[n] = lonm
            
            dist = sqrt(((lon2-lon1)**2) + ((lat2-lat2)**2))
            
            new_alt = max(alt1,alt2) + (alt_grow * dist * .1) + alt_grow
            
            if dist < 0.01:
                new_alt = max(alt1,alt2) + 1000
                if dist < 0.005:
                    new_alt = max(alt1,alt2) + 50
                    lstring_flag.append(chld1)
                    lstring_flag.append(chld2)
                    if dist < 0.0005:
                        new_alt = max(alt1,alt2) + 20
                        if dist < 0.00005:
                            new_alt = max(alt1,alt2) + 10
            altitude[n] = int(new_alt)
                
          

    #build KML
            
    kml = '<?xml version="1.0" encoding="UTF-8"?>\n <kml xmlns="http://earth.google.com/kml/2.0">\n <Document>\n\t <name>&title</name>\n'
    kml = kml.replace('&title',kml_title)

    highlight_branch_width = str(branch_width*2)
    branch_width = str(branch_width)
    style =  '\t<Style id="ICNUMa">\n' \
    '            <IconStyle>\n' \
    '                <scale>.25</scale>\n' \
    '                <Icon>\n' \
    '                    <href>ICURL</href>\n' \
    '                </Icon>\n' \
    '            </IconStyle>\n' \
    '            <LabelStyle>\n' \
    '                <scale>0</scale>\n' \
    '            </LabelStyle>\n' \
    '            <LineStyle>\n' \
    '                <width>'+branch_width+'</width>\n' \
    '            </LineStyle>\n' \
    '        </Style>\n' \
    '        <Style id="ICNUMb">' \
    '            <IconStyle>' \
    '                <scale>.95</scale>\n' \
    '                <Icon>' \
    '                    <href>ICURL</href>\n' \
    '                </Icon>\n' \
    '            </IconStyle>\n' \
    '            <LabelStyle>\n' \
    '            </LabelStyle>\n' \
    '            <LineStyle>\n' \
    '                <width>'+highlight_branch_width+'</width>\n' \
    '            </LineStyle>\n' \
    '            </Style>\n' \
    '         <StyleMap id="ICNUM">\n' \
    '            <Pair>\n' \
    '                <key>normal</key>\n' \
    '                <styleUrl>#ICNUMa</styleUrl>\n' \
    '            </Pair>\n' \
    '              <Pair>\n' \
    '                   <key>highlight</key>\n' \
    '                   <styleUrl>#ICNUMb</styleUrl>\n' \
    '              </Pair>\n' \
    '         </StyleMap>\n'


    kml += style.replace('ICURL',internal_icon).replace('ICNUM',str(0))
    
    used = {}
    used['default'] = 0
    styles = {}
    ct = 1
    for name,icon in icons.items():
        if icon in used:
            styles[name] = used[icon]
        else:
            kml += style.replace('ICURL',icon).replace('ICNUM',str(ct))
            styles[name] = ct
            used[icon] = ct
            ct+=1  
    
    kml += '<Folder>\n <name>Leaf nodes</name>\n <open>0</open>\n'


    placemark = '<Placemark id="pm_PMNAME">\n' \
    '        <name>PMNAME</name>\n' \
    '        <LookAt>\n' \
    '            <longitude>PMLON</longitude>\n' \
    '            <latitude>PMLAT</latitude>\n' \
    '            <altitude>PMALT</altitude>' \
    '            <range>500</range>\n' \
    '            <tilt>10</tilt>\n' \
    '            <heading>0</heading>\n'\
    '            <altitudeMode>absolute</altitudeMode>\n'\
    '        </LookAt>\n' \
    '        PMTIMESTAMP' \
    '        <description><![CDATA[PMCDATA]]></description>\n' \
    '        <styleUrl>STURL</styleUrl>\n' \
    '        <Style>\n' \
    '            <LineStyle>\n' \
    '            <color>PMCOLOR</color>\n' \
    '            </LineStyle>\n' \
    '        </Style>\n' \
    '        <MultiGeometry> \n' \
    '            <Point id="pt_PMNAME">\n' \
    '                <altitudeMode>relativeToGround</altitudeMode>\n' \
    '                <coordinates>PMLON,PMLAT,PMALT</coordinates>\n' \
    '            </Point>\n' \
    '            <LineString>\n' \
    '                <altitudeMode>relativeToGround</altitudeMode>\n' \
    '                <coordinates>PMLINE</coordinates>\n' \
    '            </LineString>\n' \
    '        </MultiGeometry>\n' \
    '    </Placemark>\n'
    timestamp = '<TimeStamp><when>pmtstamp</when></TimeStamp>'
    for p in leafs:
        anc = tree_struc[p]
        latitude = float(lat[p])
        longitude = float(lon[p])
        anc_lat = float(lat[anc])
        anc_lon = float(lon[anc])
        anc_alt = int(float(altitude[anc]))
        pm_color = default_color
        
        pm_cdata = '<body>'
        #build description window
        ahref = '<b>Ancestor: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(anc_lon)+'&lat='+str(anc_lat)+'&alt='+str(anc_alt)+'">HTU '+str(anc)+'</a><br>'
        pm_cdata += ahref
        
        pm_cdata += '</body>'
        
        style = styles[p]
        
        tstring = ''
        if tstamps != False:
            if p in tstamps:
                ts = tstamps[p]
                ts = ts.isoformat()
                tstring = timestamp.replace('pmtstamp',str(ts))
                
        pm = placemark.replace('PMNAME',str(p))
        pm = pm.replace('PMTIMESTAMP',tstring)
        pm = pm.replace('PMLON',str(longitude))
        pm = pm.replace('PMLAT',str(latitude))
        pm = pm.replace('STURL','#'+str(style))
        pm = pm.replace('PMALT',str(0))
        pm = pm.replace('PMCOLOR',str(pm_color))
        pm = pm.replace('PMCDATA',str(pm_cdata))
        if p in lstring_flag:
            leg = anc_alt/10
            linestring = str(longitude)+','+str(latitude)+','+str(0)+'\n'
            linestring += str(longitude)+','+str(latitude)+','+str(anc_alt-leg)+'\n'
            linestring += str(anc_lon)+','+str(anc_lat)+','+str(anc_alt-leg)+'\n'
            linestring += str(anc_lon)+','+str(anc_lat)+','+str(anc_alt)+'\n'
        else:
            linestring = get_linestring(latitude,longitude,0,anc_lat,anc_lon,anc_alt)
        pm = pm.replace('PMLINE',str(linestring))
        kml += pm

    kml += '</Folder>\n<Folder>\n<name>HTUs</name>\n <open>0</open>\n'    


    for p in nodes:
        latitude = float(lat[p])
        longitude = float(lon[p])
        alt = float(altitude[p])
        anc = tree_struc[p]
        if str(p) != str(0):
            anc_lat = float(lat[anc])
            anc_lon = float(lon[anc])
            anc_alt = float(altitude[anc])
            pm_color = default_color
            
            pm_cdata = '<body>'
            #build description window
            ahref = '<b>Ancestor: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(anc_lon)+'&lat='+str(anc_lat)+'&alt='+str(int(anc_alt))+'">HTU '+str(anc)+'</a><br>\n'
            pm_cdata += ahref
            #add link to child 1
            chld = [k for k, v in tree_struc.iteritems() if v == p][0]

            chld_lat = float(lat[chld])
            chld_lon = float(lon[chld])
            chld_alt = float(altitude[chld])
            if 0 < chld_alt:
                prefix = 'HTU '
            else:
                prefix = ''
                
            ahref = '<b>Descendant 1: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(chld_lon)+'&lat='+str(chld_lat)+'&alt='+str(int(chld_alt))+'">'+prefix+str(chld)+'</a><br>\n'
            pm_cdata += ahref
            #add link to child 2
            chld = [k for k, v in tree_struc.iteritems() if v == p][1]
            
            chld_lat = float(lat[chld])
            chld_lon = float(lon[chld])
            chld_alt = float(altitude[chld])
            if 0 < chld_alt:
                prefix = 'HTU '
            else:
                prefix = ''
                
            ahref = '<b>Descendant 2: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(chld_lon)+'&lat='+str(chld_lat)+'&alt='+str(int(chld_alt))+'">'+prefix+str(chld)+'</a><br>\n'
            pm_cdata += ahref
        
            pm_cdata += '</body>'
            
            tstring = ''
            if tstamps != False:
                if p in tstamps:
                    ts = tstamps[p]
                    ts = ts.isoformat()
                    tstring = timestamp.replace('pmtstamp',str(ts))
                
            pm = placemark.replace('PMNAME','HTU '+str(p))
            pm = pm.replace('PMTIMESTAMP',tstring)
            pm = pm.replace('PMLON',str(longitude))
            pm = pm.replace('PMLAT',str(latitude))
            pm = pm.replace('PMALT',str(int(alt)))
            pm = pm.replace('STURL','#'+str(0))
            pm = pm.replace('PMCOLOR',str(pm_color))
            pm = pm.replace('PMCDATA',str(pm_cdata))
            if p in lstring_flag:
                leg = (anc_alt-alt)/10
                linestring = str(longitude)+','+str(latitude)+','+str(alt)+'\n'
                linestring += str(longitude)+','+str(latitude)+','+str(anc_alt-leg)+'\n'
                linestring += str(anc_lon)+','+str(anc_lat)+','+str(anc_alt-leg)+'\n'
                linestring += str(anc_lon)+','+str(anc_lat)+','+str(anc_alt)+'\n'
            else:
                linestring = get_linestring(latitude,longitude,alt,anc_lat,anc_lon,anc_alt)
                
            pm = pm.replace('PMLINE',str(linestring))
        else:
            pm = '  <Placemark id="pm_PMNAME">\n' \
    '        <name>Root HTU</name>\n' \
    '        <LookAt>\n' \
    '            <longitude>PMLON</longitude>\n' \
    '            <latitude>PMLAT</latitude>\n' \
    '            <altitude>PMALT</altitude>' \
    '            <range>500</range>\n' \
    '            <tilt>10</tilt>\n' \
    '            <heading>0</heading>\n'\
    '            <altitudeMode>absolute</altitudeMode>\n'\
    '        </LookAt>\n' \
    '        <description><![CDATA[PMCDATA]]></description>\n' \
    '        <styleUrl>#0</styleUrl>\n' \
    '        <Style>\n' \
    '            <LineStyle>\n' \
    '               <color>PMCOLOR</color>\n' \
    '            </LineStyle>\n' \
    '        </Style>\n' \
    '        <MultiGeometry> \n' \
    '            <Point id="pt_PMNAME">\n' \
    '                <altitudeMode>relativeToGround</altitudeMode>\n' \
    '                <coordinates>PMLON,PMLAT,PMALT</coordinates>\n' \
    '            </Point>\n' \
    '        </MultiGeometry>\n' \
    '    </Placemark>\n'    
            pm_color = default_color
            
            pm_cdata = '<body>'
            #add link to child 1
            chld = [k for k, v in tree_struc.iteritems() if v == p][0]
            
            chld_lat = float(lat[chld])
            chld_lon = float(lon[chld])
            chld_alt = float(altitude[chld])
            if 0 < chld_alt:
                prefix = 'HTU '
            else:
                prefix = ''
                
            ahref = '<b>Descendant 1: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(chld_lon)+'&lat='+str(chld_lat)+'&alt='+str(chld_alt)+'">'+prefix+str(chld)+'</a><br>\n'
            pm_cdata += ahref
            #add link to child 2
            chld = [k for k, v in tree_struc.iteritems() if v == p][1]
            
            chld_lat = float(lat[chld])
            chld_lon = float(lon[chld])
            chld_alt = float(altitude[chld])
            if 0 < chld_alt:
                prefix = 'HTU '
            else:
                prefix = ''
                
            ahref = '<b>Descendant 2: </b><a href="'+str(mydomain)+'/flyto.kml?lon='+str(chld_lon)+'&lat='+str(chld_lat)+'&alt='+str(chld_alt)+'">'+prefix+str(chld)+'</a><br>\n'
            pm_cdata += ahref
            
            pm_cdata += '</body>'

            pm = pm.replace('PMNAME',str(p))
            pm = pm.replace('PMLON',str(longitude))
            pm = pm.replace('PMLAT',str(latitude))
            pm = pm.replace('PMALT',str(alt))
            pm = pm.replace('PMCOLOR',str(pm_color))
            pm = pm.replace('PMCDATA',str(pm_cdata))
            
            
            tstring = ''
            if tstamps != False:
                if p in tstamps:
                    ts = tstamps[p]
                    ts = ts.isoformat()
                    tstring = timestamp.replace('pmtstamp',str(ts))
            pm = pm.replace('PMTIMESTAMP',tstring)
            
            
        kml += pm
    kml += '</Folder>\n</Document>\n</kml>'  
    
    return kml,len(leafs)
        
        
